//
//  88. 合并两个有序数组.swift
//  Top600
//
//  Created by rjb on 2021/8/8.
//

import Foundation
class Solution88 {
    // 合并两个有序数组
    // 如果将第二个往第一个插入的话会造成很多移动
    // 可以nums1的后面为基准从后向前填入
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        var p1 = m - 1
        var p2 = n - 1
        for i in (0..<nums1.count).reversed() {
            var v1 = Int.min
            var v2 = Int.min
            if p1 >= 0 {
                v1 = nums1[p1]
            }
            if p2 >= 0 {
                v2 = nums2[p2]
            }
            // 选中大的填入
            if v1 > v2 {
                nums1[i] = v1
                p1 -= 1
            } else {
                nums1[i] = v2
                p2 -= 1
            }
        }
    }
    static func test() {
        let solution = Solution88()
        var nums1 = [1,2,3,0,0,0]
        let nums2 = [2,5,6]
        let m = 3
        let n = 3
        solution.merge(&nums1, m, nums2, n)
        print(nums1)
    }
}
